package src;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Vector;

/*
 * GeneradorPermutaciones
 * Genera todas la permutaciones de una lista de n elementos
 * 
 */


public class GeneradorPermutaciones {

  private Integer[] a;
  private BigInteger faltan;
  private BigInteger total;

	public static void main(String[] args) 
	{
		//ArrayList<int[]> res = generarPermutaciones(5);
		int[] a = {1,2,3,4,5};
		ArrayList<Integer[]> res = generarPermutaciones(a.length);

		for (int i = 0; i < res.size(); i++) 
		{
			StringBuffer sb = new StringBuffer("[ ");
			for (int j = 0; j < res.get(i).length; j++) 
			{
				sb.append(res.get(i)[j] + " " );
			}
			sb.append(" ]");
			System.out.println(sb.toString());
		}
		System.out.println("-----------------> cant permutaciones = " + res.size());
	}
    
	
	// devuelve null en caso de que la permutacion pasada por parametro no es valida (contiene repetidos)
	public static ArrayList<Integer[]> generarPermutacionesDelResto(Integer[] elems)
	{
		// SI RECIBO [2 0 0 0] lo transformo a [2], si hay dos repetidos (distintos de cero), no es valido
		ArrayList<Integer[]> todasLasPermutaciones = null;
		ArrayList<Integer[]> permutacionesB = null;
		
		if (noTieneRepetidos(elems))
		{
			if(tieneAlMenosUnCero(elems))
				elems = redimensiono(elems.clone());
			Ej2.cantOp++;			
			todasLasPermutaciones = new ArrayList<Integer[]>();
			permutacionesB = new ArrayList<Integer[]>();
			Ej2.cantOp++;
			todasLasPermutaciones = generarPermutaciones(elems.length);
			Ej2.cantOp++;
			Integer[] tmp = new Integer[elems.length];
			for (int i = 0; i < todasLasPermutaciones.size(); i++) // .............................. n*n!
			{
				for (int j = 0; j < todasLasPermutaciones.get(i).length; j++) 
				{
					Ej2.cantOp++;
					tmp[j] = elems[todasLasPermutaciones.get(i)[j] - 1];
				}
				permutacionesB.add(tmp.clone());
				Ej2.cantOp++;
			}
		}
		
		return permutacionesB;
	}
	
	public static Integer[] redimensiono(Integer[] e)
	{
		Vector<Integer> r = new Vector<Integer>();
		for (int i = 0; (i < e.length) && (e[i] != 0); i++) 
		{
			r.add(e[i]);
		}
		Integer[] res = new Integer[r.size()];
		for (int i = 0; i < res.length; i++) 
		{
			res[i] = 0;
		}
		for (int j = 0; j < r.size(); j++) 
		{
			res[j] = r.get(j);
		}
		return res;
	}
	
	public static boolean tieneAlMenosUnCero(Integer[] a)
	{
		int i;
		for (i = 0; ((i < a.length) && (a[i] != 0)); i++){
			Ej2.cantOp++;
		} 
		return (i != a.length);
	}
	
	/***
	 * @param elems un array
	 * 
	 * @return true si hay elems distintos de cero repetidos, false en otro caso
	 */
	public static boolean noTieneRepetidos(Integer[] elems)
	{
		boolean res = true;
		Integer[] countElems = new Integer[maximo(elems)+1];
		for (int i = 0; i < countElems.length; i++) 
		{
			Ej2.cantOp++;
			countElems[i] = 0;
		}
		for (int i = 0; i < elems.length; i++) 
		{
			countElems[elems[i]]++;
			Ej2.cantOp++;
			if(countElems[elems[i]]>1 && (elems[i] != 0))
			{
				res = false;
				Ej2.cantOp++;
				break;
			}
		}
				
		return res;
	}
	
	/**
	 * 
	 * @param elems un array
	 * @return el maximo elem de un array
	 */
	public static Integer maximo (Integer[] elems)
	{
		Integer max = elems[0]; 
		for (int i = 1; i < elems.length; i++) 
		{
			if(max < elems[i])
				max = elems[i];
		}
		return max;
	}
	
	public static ArrayList<Integer[]> generarPermutaciones(int n)
	{
		ArrayList<Integer[]> todasLasPermutaciones = new ArrayList<Integer[]>();
		GeneradorPermutaciones prueba = new GeneradorPermutaciones(n);
		
		Integer[] permutacion;
		while(prueba.tienePermutaciones())
		{
			permutacion = prueba.getNext();
			todasLasPermutaciones.add(permutacion.clone());
		}
		
		return todasLasPermutaciones;
	}
	
	public GeneradorPermutaciones (int n) {
    if (n < 1) {
      throw new IllegalArgumentException ("Min 1");
    }
    a = new Integer[n];
    Ej2.cantOp++;
    total = getFactorial (n);
    reset();
  }
	
  public boolean tienePermutaciones () {
	    return faltan.compareTo (BigInteger.ZERO) == 1;
	  }
  

  public BigInteger getFaltan () {
    return faltan;
  }

  //------------------------------------
  // Devuelve el numero total de permutaciones


  public BigInteger getTotal () {
    return total;
  }
  
  //------
  // Reset
  //------

  public void reset () {
    for (int i = 0; i < a.length; i++) 
      a[i] = i + 1 ;

    faltan = new BigInteger (total.toString ());
  }

  //-----------------------------
  // Quedan permutaciones por generar?


  private static BigInteger getFactorial (int n) {
    BigInteger fact = BigInteger.ONE;
    for (int i = n; i > 1; i--) {
      fact = fact.multiply (new BigInteger (Integer.toString (i)));
    }
    return fact;
  }

  //--------------------------------------------------------
  // Genera la sgte permutacion (algorithm from Rosen)


  public Integer[] getNext () {

    if (faltan.equals (total)) {
      faltan = faltan.subtract (BigInteger.ONE);
      return a;
    }

    int temp;

    // Encuentra el mayor indice j with a[j] < a[j+1]

    int j = a.length - 2;
    while (a[j] > a[j+1]) {
      j--;
    }

    // Encuentra el indice k tq a[k] es el entero mas chico mayor 
    // a a[j] a la derecha de a[j]
    int k = a.length - 1;
    while (a[j] > a[k]) {
      k--;
    }

    // Swappea a[j] y a[k]

    temp = a[k];
    a[k] = a[j];
    a[j] = temp;


    int r = a.length - 1;
    int s = j + 1;

    while (r > s) {
      temp = a[s];
      a[s] = a[r];
      a[r] = temp;
      r--;
      s++;
    }

    faltan = faltan.subtract (BigInteger.ONE);
    return a;

  }

}